#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
long long n,m,p,q,w,root,ans,o,z[N],x,oo,ooo,oooo,l,r,mid,sum,top,sum1,sum2,pop=1e18,sum4,sum5;
struct node{
	long long l,r,z,k,sum,siz,sum2,sum3;
}treap[N];
inline long long mke(long long i)
{
	if(top) w=z[top],--top;
	else ++o,w=o;
	treap[w].z=treap[w].sum=treap[w].sum2=treap[w].sum3=i;
	treap[w].l=treap[w].r=0;
	treap[w].siz=1;
	treap[w].k=rand();
	return w;
}
inline void gx(long long i)
{
	treap[i].sum=treap[i].z+treap[treap[i].l].sum+treap[treap[i].r].sum;
	treap[i].siz=1+treap[treap[i].l].siz+treap[treap[i].r].siz;
	treap[i].sum2=treap[treap[i].l].sum2+treap[treap[i].r].sum2+(treap[treap[i].r].siz+1)*(treap[i].z+treap[treap[i].l].sum);
	treap[i].sum3=treap[treap[i].l].sum3+treap[treap[i].r].sum3+(treap[treap[i].l].siz+1)*(treap[i].z+treap[treap[i].r].sum);
}
inline void spilt(long long i,long long j,long long &l,long long &r)
{
	if(!i)
	{
		l=r=0;
		return;
	}
	if(treap[i].z<=j)
	{
		l=i;
		spilt(treap[l].r,j,treap[l].r,r);
		gx(l);
	}
	else{
		r=i;
		spilt(treap[r].l,j,l,treap[r].l);
		gx(r);
	}
}
inline long long marge(long long l,long long r)
{
	if(!l||!r)
		return l+r;
	if(treap[l].k>=treap[r].k)
	{
		treap[l].r=marge(treap[l].r,r);
		gx(l);
		return l;
	}
	else{
		treap[r].l=marge(l,treap[r].l);
		gx(r);
		return r;
	}
}
inline long long cx(long long i,long long j)
{
	if(j>treap[i].siz) return 0;
	while(1)
	{
		if(treap[treap[i].l].siz<j)
		{
			if(treap[i].l) j-=treap[treap[i].l].siz;
			if(j<=1) return i;
			--j;
			i=treap[i].r;
		}
		else
			i=treap[i].l;
	}
}
int main()
{
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>x;
		oo=ooo=oooo=0;
		spilt(root,x-1,oo,ooo);
		spilt(ooo,x,ooo,oooo);
		if(treap[ooo].siz)
		{
			root=marge(oo,oooo);
			++top;
			z[top]=ooo;
		}
		else
			root=marge(oo,marge(mke(x),oooo));
		l=2,r=treap[root].siz/2,ans=1;
		if(treap[root].siz>4)
		{
			mid=2;
			p=cx(root,mid);
			q=cx(root,treap[root].siz-mid+2);
			oo=ooo=oooo=0;
			spilt(root,treap[p].z,oo,ooo);
			sum1=treap[oo].sum;
			if(!q) spilt(ooo,pop,ooo,oooo);
			else spilt(ooo,treap[q].z-1,ooo,oooo);
			sum2=treap[oooo].sum;
			if(sum1>sum2)
				ans=mid,l=mid+1;
			else
				r=mid-1;
			root=marge(oo,marge(ooo,oooo));
		}
		while(l<=r)
		{
			mid=(l+r)>>1;
			p=cx(root,mid);
			q=cx(root,treap[root].siz-mid+2);
			oo=ooo=oooo=0;
			spilt(root,treap[p].z,oo,ooo);
			sum1=treap[oo].sum;
			if(!q) spilt(ooo,pop,ooo,oooo);
			else spilt(ooo,treap[q].z-1,ooo,oooo);
			sum2=treap[oooo].sum;
			if(sum1>sum2)
				ans=mid,l=mid+1;
			else
				r=mid-1;
			root=marge(oo,marge(ooo,oooo));
		}
		if(ans==treap[root].siz/2)
			ans=treap[root].siz;
//		sum=-treap[cx(root,1)].z;
		p=cx(root,ans);
		q=cx(root,treap[root].siz-ans+2);
		sum=treap[root].sum;
		oo=ooo=0;
		spilt(root,treap[p].z,oo,ooo);
		sum1=treap[oo].sum2;
		root=marge(oo,ooo);
//		cout<<q<<" ";
		ooo=oooo=0;
		if(!q) spilt(root,pop,ooo,oooo);
		else spilt(root,treap[q].z-1,ooo,oooo);
		sum2=treap[oooo].sum3;
		root=marge(ooo,oooo);
		if(ans==1) cout<<max(0ll,sum-sum1*2)<<'\n';
		else
		{
//			sum=-treap[cx(root,1)].z;
			ans=treap[root].siz;
			p=cx(root,ans);
			q=cx(root,treap[root].siz-ans+2);
			oo=ooo=0;
			spilt(root,treap[p].z,oo,ooo);
			sum4=treap[oo].sum2;
			root=marge(oo,ooo);
//			cout<<q<<" ";
			ooo=oooo=0;
			if(!q) spilt(root,pop,ooo,oooo);
			else spilt(root,treap[q].z-1,ooo,oooo);
			sum5=treap[oooo].sum3;
			root=marge(ooo,oooo);
			cout<<max(0ll,max(sum-sum4-sum5,sum-sum1+sum2))<<'\n';
		 } 
	}
	return 0;
 } 
